/**
 * 
 */
package leetCode;

/**
 * @author zhongfang
 *
 */
public class KnightProbabilityinChessboard {
	final int[][] change = { { 1, 2 }, { 2, 1 }, { 1, -2 }, { 2, -1 }, { -1, 2 }, { -2, 1 }, { -1, -2 }, { -2, -1 } };

	public double knightProbability(int N, int K, int r, int c) {
		double[][][] dp = new double[K + 1][N][N];
		return helper(dp, N, r, c, K);
	}

	private double helper(double[][][] dp, int n, int r, int c, int k) {
		if (dp[k][r][c] != 0) {
			return dp[k][r][c];
		}
		if (k == 0) {
			dp[k][r][c] = 1;
			return 1;
		}
		for (int[] pos : change) {
			int newX = r + pos[0];
			int newY = c + pos[1];
			if (newX < n && newX >= 0 && newY < n && newY >= 0) {
				dp[k][r][c] += helper(dp, n, newX, newY, k - 1) / 8;
			}
		}
		return dp[k][r][c];
	}

	public double knightProbability2(int N, int K, int r, int c) {
		final int[][] change = { { 1, 2 }, { 2, 1 }, { 1, -2 }, { 2, -1 }, { -1, 2 }, { -2, 1 }, { -1, -2 },
				{ -2, -1 } };
		double dp[][] = new double[N][N];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				dp[i][j] = 1;
			}
		}

		for (int k = 0; k < K; k++) {
			double tmp[][] = new double[N][N];
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					for (int[] pos : change) {
						int newX = i + pos[0];
						int newY = j + pos[1];
						if (newX < N && newX >= 0 && newY < N && newY >= 0) {
							tmp[i][j] += 1.0 / 8 * dp[newX][newY];
						}
					}
				}
			}
			dp = tmp;
		}
		return dp[r][c];
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		System.out.println(new KnightProbabilityinChessboard().knightProbability(3, 2, 0, 0));
	}

}
